﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows;

namespace WpfPaintPolygon
{
    public static class ClippingEar
    {
        /// <summary>
        /// Triangulates the specified points.
        /// </summary>
        /// <param name="points">The points.</param>
        public static IList<IList<Point>> Triangulate(IList<Point> points)
        {
            // zdrojovy seznam bodu
            IList<Point> source = null;

            // seznam seznamu bodu
            IList<IList<Point>> result = new List<IList<Point>>();

            // kontrola, zdali jde polygon nakreslen po smeru, ci proti smeru hod. rucicek
            // jde pouze o znamenko plochy
            // potrebujeme, aby byl polygon tvoren protismeru hod. rucicek 
            if (AreaPolygon(points) > 0)
            {
                // nemusime otacet, staci pouzit zdrojove
                source = new List<Point>(points);
            }
            else
            {
                // obratime poradi
                source = new List<Point>(points.Reverse());
            }

            int x = 0;
            // odrezavame usi, dokud nam nezbyde jeden trojuhelnik
            while (source.Count > 3)
            {
                // vytazeni bodu
                Point p0 = source[(x - 1 + source.Count) % source.Count];
                Point p1 = source[(x) % source.Count];
                Point p2 = source[(x + 1) % source.Count];

                // zkontrolujeme, zdali P1 je nalevo nebo napravo
                if (IsLeft(p0, p2, p1) < 0)
                {
                    // pokud je vlevo, je treba zkontroloval zdali trojuhelnik neprochazi zkrz existujici hrany
                    bool isOk = true;

                    // projedeme vsechny body a budeme kontrolovat, zdali se nachazi uvnitr noveho trojuhelniku
                    foreach (Point p in source)
	                {
                        // pouzite body automaticky preskocime
		                if (p == p0 || p == p1 || p == p2) continue;
                        // pokud je uvnitr, nastavime flaf isOk na false
                        if (IsInsideTriangle(p0,p1,p2, p)) isOk = false;
	                }

                    // pokud je vse v poradku, tak vygenerujeme trojuhelnik
                    if (isOk)
                    {
                        result.Add(new List<Point>() { p0, p1, p2 });
                        source.Remove(p1);
                    }
                }

                x++;
            }

            result.Add(source);

            return result;
        }

        /// <summary>
        /// Determines whether [is inside triangle] [the specified a].
        /// http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml
        /// </summary>
        /// <param name="a">A.</param>
        /// <param name="b">The b.</param>
        /// <param name="c">The c.</param>
        /// <param name="p">The p.</param>
        /// <returns>
        ///   <c>true</c> if [is inside triangle] [the specified a]; otherwise, <c>false</c>.
        /// </returns>
        public static bool IsInsideTriangle(Point a, Point b, Point c, Point p)
        {
            double ax, ay, bx, by, cx, cy, apx, apy, bpx, bpy, cpx, cpy;
            double cCROSSap, bCROSScp, aCROSSbp;

            ax = c.X - b.X; ay = c.Y - b.Y;
            bx = a.X - c.X; by = a.Y - c.Y;
            cx = b.X - a.X; cy = b.Y - a.Y;
            apx = p.X - a.X; apy = p.Y - a.Y;
            bpx = p.X - b.X; bpy = p.Y - b.Y;
            cpx = p.X - c.X; cpy = p.Y - c.Y;

            aCROSSbp = ax * bpy - ay * bpx;
            cCROSSap = cx * apy - cy * apx;
            bCROSScp = bx * cpy - by * cpx;

            return ((aCROSSbp >= 0.0f) && (bCROSScp >= 0.0f) && (cCROSSap >= 0.0f));
        }

        /// <summary>
        /// Determines whether the specified p2 is left.
        /// http://geomalgorithms.com/a01-_area.html
        /// Rozhodnuti, zdali je P2 od orientovane usecky (P0, P1):
        /// nalevo - result > 0
        /// na spojnici - result = 0
        /// napravo - result < 0
        /// </summary>
        /// <param name="p0">The p0.</param>
        /// <param name="p1">The p1.</param>
        /// <param name="p2">The p2.</param>
        /// <returns></returns>
        public static double IsLeft(Point p0, Point p1, Point p2)
        {
            return ((p1.X - p0.X) * (p2.Y - p0.Y)
                - (p2.X - p0.X) * (p1.Y - p0.Y));
        }

        /// <summary>
        /// Areas the specified points.
        /// http://www.computational-geometry.org/mailing-lists/compgeom-announce/2003-November/000837.html
        /// </summary>
        /// <param name="points">The points.</param>
        /// <returns></returns>
        public static double AreaPolygon(IList<Point> points)
        {
            double area = 0;
            for (int i = 0; i < points.Count - 1; i++)
            {
                area += (points[i].X - points[i + 1].X) * (points[i].Y + points[i + 1].Y);
            }
            area *= 0.5;
            return area;
        }

        /// <summary>
        /// Lines the intersect.
        /// Based on:
        /// http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=geometry2
        /// </summary>
        /// <param name="x1">The x1.</param>
        /// <param name="x2">The x2.</param>
        /// <param name="y1">The y1.</param>
        /// <param name="y2">The y2.</param>
        /// <param name="intersect">The intersect.</param>
        /// <returns></returns>
        public static bool LineIntersect(Point x1, Point x2, Point y1, Point y2, out Point intersect)
        {
            intersect = new Point();
            // prvni usecka
            double a1 = x2.Y - x1.Y;
            double b1 = x1.X - x2.X;
            double c1 = a1 * x1.X + b1 * x1.Y;

            // druha usecka
            double a2 = y2.Y - y1.Y;
            double b2 = y1.X - y2.X;
            double c2 = a2 * y1.X + b2 * y1.Y;

            double det = a1 * b2 - a2 * b1;

            // nejsou rovnobezky
            if (det != 0)
            {
                double x = (b2 * c1 - b1 * c2) / det;
                double y = (a1 * c2 - a2 * c1) / det;

                // pokud je prusecik mezi body, tak true
                if (Math.Min(x1.X, x2.X) <= x && x <= Math.Max(x1.X, x2.X)
                    && Math.Min(y1.Y, y2.Y) <= y && y <= Math.Max(y1.Y, y2.Y))
                {
                    intersect.X = x;
                    intersect.Y = y;

                    return true;
                }
            }

            return false;
        }
    }
}
